/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.Iterator;
import java.util.NoSuchElementException;

import mosdi.fa.Alphabet;

/** Class that generates all abelian patterns over the iupac alphabet that
 *  satisfy the given restrictions. The patterns are returned by means of 
 *  a frequency vector.
 */
public class IupacAbelianPatternGenerator implements Iterable<int[]> {
	private int length;
	private Alphabet alphabet;
	private int[] minFrequency;
	private int[] maxFrequency;
	private double maxProb;
	
	public IupacAbelianPatternGenerator(int length, int[] minFrequency, int[] maxFrequency, double maxProb) {
		if ((minFrequency.length!=4) || (maxFrequency.length!=4) || (length<1)) throw new IllegalArgumentException();
		this.length = length;
		this.alphabet = Alphabet.getIupacAlphabet();
		this.minFrequency = minFrequency;
		this.maxFrequency = maxFrequency;
		this.maxProb = maxProb;
	}
	
	/** Returns the iupac alphabet. */
	public Alphabet getAlphabet() { return alphabet; }
	
	private class IupacAbelianPatternIterator implements Iterator<int[]> {
		int[][] charSets;
		// high-level segmentation, i.e. how many chars come from each charset
		Iterator<int[]> segmentationIterator;
		// current segmentation
		int[] segmentation;
		// for each high-level segment an iterator over the corresponding low-level segment,
		// i.e. iterators telling which chars come from each charset
		Iterator<int[]>[] subSegmentationIterators;
		int[] current;
		
		@SuppressWarnings("unchecked")
		public IupacAbelianPatternIterator() {
			int[][] charSets = {
				{alphabet.getIndex('A'), alphabet.getIndex('C'), alphabet.getIndex('G'), alphabet.getIndex('T')},
				{alphabet.getIndex('R'), alphabet.getIndex('Y'), alphabet.getIndex('S'), alphabet.getIndex('W'), alphabet.getIndex('K'), alphabet.getIndex('M')},
				{alphabet.getIndex('B'), alphabet.getIndex('D'), alphabet.getIndex('H'), alphabet.getIndex('V')},
				{alphabet.getIndex('N')},
			};
			this.charSets = charSets;
			try {
				current = new int[alphabet.size()];
				segmentationIterator = new SegmentationGenerator(length, maxFrequency, minFrequency).iterator();
				segmentation = getNextSegmentation();
				subSegmentationIterators = new Iterator[charSets.length];
				for (int i=0; i<charSets.length; ++i) {
					initSubSegmentationIterator(i);
					applyNextSubSegmentation(i);
				}
			} catch (NoSuchElementException e) {
				current = null;
			}
		}
		
		private void initSubSegmentationIterator(int pos) {
			if (segmentation[pos]>0) {
				subSegmentationIterators[pos] = new SegmentationGenerator(segmentation[pos],charSets[pos].length).iterator();
			} else {
				subSegmentationIterators[pos] = null;
			}
		}
		
		private void applyNextSubSegmentation(int pos) {
			if (subSegmentationIterators[pos]==null) {
				for (int c : charSets[pos]) current[c]=0;
			} else {
				int[] subSegmentation = subSegmentationIterators[pos].next();
				for (int i=0; i<charSets[pos].length; ++i) {
					current[charSets[pos][i]]=subSegmentation[i];
				}
			}
		}
		
		public boolean hasNext() {
			return current!=null;
		}

		/** Get next segmentation from segmentationIterator that does conform 
		 *  with maxProb. */
		private int[] getNextSegmentation() throws NoSuchElementException {
			if (maxProb==1.0) return segmentationIterator.next();
			int[] segmentation = null;
			while (true) {
				segmentation = segmentationIterator.next();
				// calculate probability for a string with this composition
				// and compare it to maxProb
				double p = 1.0;
				for (int i=0; i<4; ++i) {
					p*=Math.pow((1.0+i)/4.0, segmentation[i]);
				}
				if (p<=maxProb) break;
			}
			return segmentation;
		}
		
		public int[] next() {
			if (current==null) throw new NoSuchElementException();
			// copy current to result
			int[] result = new int[current.length];
			System.arraycopy(current, 0, result, 0, current.length);
			// position in array of subSegmentationIterators
			int pos = segmentation.length-1;
			while (subSegmentationIterators[pos]==null) --pos;
			// backtracking ...
			while (!subSegmentationIterators[pos].hasNext()) {
				--pos;
				while ((pos>=0) && (subSegmentationIterators[pos]==null)) --pos;
				if (pos<0) {
					try {
						segmentation = getNextSegmentation();
						current = new int[alphabet.size()];
						pos = 0;
						while (segmentation[pos]==0) ++pos;
						initSubSegmentationIterator(pos);
						break;
					} catch (NoSuchElementException e) {
						current = null;
						return result;
					}
				}
			}
			// advance at current position
			applyNextSubSegmentation(pos++);
			// go forward ...
			for (;pos<segmentation.length; ++pos) {
				if (segmentation[pos]!=0) {
					initSubSegmentationIterator(pos);
					applyNextSubSegmentation(pos);
				}
			}
			return result;
		}

		public void remove() { throw new UnsupportedOperationException(); }
	}

	
	public Iterator<int[]> iterator() {
		return new IupacAbelianPatternIterator();
	}

}
